#include <stdio.h>
#include <limits.h>

#define MAX(a,b) (a)>(b)?(a):(b)

int main(){
	int mn = 5, pn = 10; //金矿数量，人的数量
	int np[] = {5,3,4,3,5};//每个金矿需要的人
	int mv[] = {500,200,300,350,400};//每个金矿的收益
	int result[pn];//最终结果
	int t, i, j;
	for(i = 0; i < pn; ++i)
		result[i] = mv[i];
	for(i = 0; i < mn; ++i){
		for(j = 0; j < pn; ++j){
            if(j-np[i] < 0)
                t = INT_MIN;
            else
                t = result[j-np[i]];
            result[j] = MAX(result[j], t+mv[i]);
        }
	}
	for(i = 0; i < pn; ++i)
        printf("%d  ", result[i]);
	printf("\n");
	return 0;
}